home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 / Ham Radio 2000.iso / ham2000 / satellit / kissfilt / re.doc < prev   
Text File  |  1991-04-22  |  5KB  |  97 lines
  1. [ This file is extracted from Henry Spencer's man page for his
  2.   regular expression matching package.  -KB5MU]
  3.  
  4. DESCRIPTION
  5.      These functions implement egrep(1)-style regular expressions
  6.      and supporting facilities.
  7.  
  8. REGULAR EXPRESSION SYNTAX
  9.      A regular expression is zero or more branches, separated  by
  10.      `|'.  It matches anything that matches one of the branches.
  11.  
  12.      A branch is zero or more pieces, concatenated.  It matches a
  13.      match  for  the  first,  followed by a match for the second,
  14.      etc.
  15.  
  16.      A piece is an atom possibly followed by `*',  `+',  or  `?'.
  17.      An  atom  followed  by  `*'  matches a sequence of 0 or more
  18.      matches of the atom.  An atom  followed  by  `+'  matches  a
  19.      sequence of 1 or more matches of the atom.  An atom followed
  20.      by `?' matches a match of the atom, or the null string.
  21.  
  22.      An atom is a regular expression in parentheses  (matching  a
  23.      match  for the regular expression), a range (see below), `.'
  24.      (matching any single  character),  `^'  (matching  the  null
  25.      string  at the beginning of the input string), `$' (matching
  26.      the null string at the end of the input string), a `\'  fol-
  27.      lowed  by a single character (matching that character), or a
  28.      single character with no other significance  (matching  that
  29.      character).
  30.  
  31.      A range is a sequence of characters enclosed  in  `[]'.   It
  32.      normally matches any single character from the sequence.  If
  33.      the sequence begins with `^', it matches any single  charac-
  34.      ter not from the rest of the sequence.  If two characters in
  35.      the sequence are separated by `-', this is shorthand for the
  36.      full  list  of  ASCII  characters between them (e.g. `[0-9]'
  37.      matches any decimal digit).  To include a literal `]' in the
  38.      sequence,  make it the first character (following a possible
  39.      `^').  To include a literal `-', make it the first  or  last
  40.      character.
  41.  
  42. AMBIGUITY
  43.      If a regular expression could match two different  parts  of
  44.      the  input string, it will match the one which begins earli-
  45.      est.  If both begin in the same place        but match  dif-
  46.      ferent  lengths, or match the same length in different ways,
  47.      life gets messier, as follows.
  48.  
  49.      In general, the possibilities in a list of branches are con-
  50.      sidered  in  left-to-right order, the possibilities for `*',
  51.      `+', and `?' are considered longest-first, nested constructs
  52.      are  considered from the outermost in, and concatenated con-
  53.      structs are considered leftmost-first.  The match that  will
  54.      be  chosen  is the one that uses the earliest possibility in
  55.      the first choice that has to be made.  If there is more than
  56.      one choice, the next will be made in the same manner (earli-
  57.      est possibility)  subject  to  the  decision  on  the  first
  58.      choice.  And so forth.
  59.  
  60.      For example, `(ab|a)b*c' could match `abc'  in  one  of  two
  61.      ways.   The first choice is between `ab' and `a'; since `ab'
  62.      is earlier, and does lead to a successful overall match,  it
  63.      is  chosen.   Since  the `b' is already spoken for, the `b*'
  64.      must match its last possibility-the  empty  string-since  it
  65.      must respect the earlier choice.
  66.  
  67.      In the particular case where no `|'s are present  and  there
  68.      is  only  one  `*',  `+', or `?', the net effect is that the
  69.      longest possible match will be chosen.  So `ab*',  presented
  70.      with  `xabbbby',  will match `abbbb'.  Note that if `ab*' is
  71.      tried against `xabyabbbz', it will  match  `ab'  just  after
  72.      `x', due to the begins-earliest rule.  (In effect, the deci-
  73.      sion on where to start the match is the first choice  to  be
  74.      made,  hence subsequent choices must respect it even if this
  75.      leads them to less-preferred alternatives.)
  76.  
  77. HISTORY
  78.      Both code and manual page were written at U of T.  They  are
  79.      intended  to  be  compatible with the Bell V8 regexp(3), but
  80.      are not derived from Bell code.
  81.  
  82. BUGS
  83.      Empty branches and empty regular expressions are  not  port-
  84.      able to V8.
  85.  
  86.      The restriction against applying `*' or `+' to  a  possibly-
  87.      null  operand  is  an artifact of the simplistic implementa-
  88.      tion.
  89.  
  90.      Does not support egrep's newline-separated branches; neither
  91.      does the V8 regexp(3), though.
  92.  
  93.      Due to emphasis on  compactness  and  simplicity,  it's  not
  94.      strikingly fast.  It does give special attention to handling
  95.      simple cases quickly.
  96.  
  97.